package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
 * 执行用时：4 ms, 在所有 Java 提交中击败了99.43%的用户
 * 内存消耗：40.3 MB, 在所有 Java 提交中击败了30.10%的用户
 **/
public class No012 {

    private char[][] board;
    private char[] chars;

    public boolean exist(char[][] board, String word) {
        char[] chars = word.toCharArray();
        this.board = board;
        this.chars = chars;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(i, j, 0)) return true;
            }
        }
        return false;
    }

    public boolean dfs(int i, int j, int k) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != chars[k]) return false;
        if (k == chars.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1);
        board[i][j] = chars[k];
        return res;
    }
}
